package leetcode.ReverseLinkedList;

/**
 * @Auther: xujianfeng
 * @Date: 2018/8/27 21:03
 * @Description:
 */
public class ReverseLinkedList {

    public static void main(String args[]) {
        ListNode a = new ListNode(1);
        ListNode b = new ListNode(2);
        ListNode c = new ListNode(3);
        ListNode d = new ListNode(4);
        ListNode e = new ListNode(5);

        a.next = b;
        b.next = c;
        c.next = d;
        d.next = e;
        ListNode head = a;
        while (head != null) {
            System.out.println(head.val);
            head = head.next;
        }
        ListNode reverse = reverseList1(a);

        while (reverse != null) {
            System.out.println(reverse.val);
            reverse = reverse.next;
        }

    }

    public static ListNode reverseList1(ListNode head) { //迭代
        ListNode newhead = null;
        ListNode now;
        while (head != null) {
            now = head;         //取头
            head = head.next;   //更新原链头
            now.next = newhead; //插入新链
            newhead = now;      //更新新链头
        }
        return newhead;
    }

    public static ListNode reverseList(ListNode head) { //递归
        if (head == null || head.next == null)
            return head;
        ListNode newhead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newhead;
    }
}

